This invention relates to pattern analysis and recognition and, more particularly, to systems for thinning or skeletonizing the strokes of imaged symbols, characters or binary-values images in general, that can be used in the classification process. This invention is related to an application, filed on even date herewith, entitled "Imaged Symbol Classification".
A wide variety of applications exist in which it is desirable for a machine to automatically recognize, analyze and classify character patterns in a given image. The explosion of computer-based information gathering, handling, manipulation, storage, and transmission systems offers the technology that makes the realization of these desires possible. Elaborate programs have been written for general purpose computers to perform pattern recognition, but they have experienced a limited level of success. That success was achieved mostly in the area of recognizing standard printed fonts.
One character recognition technique that dates back to the early 1960's involves following the curve of the characters to be recognized. It has an intuitive appeal but, unfortunately, it often fails when the characters are misshapen or have extraneous strokes.
Bakis et al. (IBM) reported on an approach for recognizing hand-printed numerals in an article titled "An Experimental Study of Machine Recognition of Hand Printed Numerals," IEEE Transactions on Systems Science and Cybernetics Vol SSC-4, No. 2, July 1968. In the described system, the numerals are converted into a 25.times.32 binary matrix. Features are extracted to reduce the dimensionality of the 800 bit vector (25.times.32) to about 100, and the 100 bit vector is submitted to several categorizers. Some "normalization" of the characters is also performed. The authors reported a recognition rate of between 86 to 99.7 percent, depending on the handwriting samples employed. Because of the low recognition rate relative to the desired level for commercial applications, the authors concluded that "it would seem that the course to follow is to combine curve-following type measurements . . . with automatic feature selection and parallel decision logic."
In what appears to be a follow-up effort, R. G. Casey described an experiment that expanded the "normalization" of Bakis et al. to a process of deskewing of the subject characters. "Moment Normalization of Handprinted Characters", IBM Journal of Research Development, September, 1970, pp 548-557. Casey used feature recognition in combination with curve following, as suggested by Bakis et al., and decision methodologies which included template matching, clustering, autocorrelation, weighted cross correlation, and zoned n-tuples.
In a subsequent article, Naylor (also of IBM) reported on an OCR (Optical Character Recognition) system that employs a computer, an interactive graphics console, and skew normalization. "Some Studies in the Interactive Design of Character Recognition Systems", IEEE Transactions on Computers, September, 1971, pp 1075-1086. The objective of his system was to develop the appropriate logic for identifying the features to be extracted.
In U.S. Pat. No. 4,259,661 issued Mar. 31, 1981, another extracted-feature approach was described by Todd. In accordance with the Todd approach, a rectangular area defined by the character's extremeties is normalized to a predefined size, and then divided into subareas. The "darkness" of the image within each of the subareas is evaluated, and the collection of the darkness evaluations is formed into a "feature vector." The feature vector is compared to a stored set of feature vectors that represent characters, and the closest match is selected as the recognized character.
In an article entitled "SPTA: A Proposed Algorithm for Thinning Binary Patterns", IEEE Transaction on Systems, Man, and Cybernetics, Vol. SMC-14, No. 3, May/June 1984, pp. 409-418, Naccache et al. present a different approach to the OCR problem. This approach addresses the fact that patterns are often made up of strokes that are wide, and that it may be of benefit to skeletonize the patterns. As described by Naccache et al, "skeletonization consists of iterative deletions of the dark points (i.e., changing them to white) along edges of a pattern until the pattern is thinned to a line drawing." Ideally, the original pattern is thinned to its medial axis. The article briefly describes fourteen different known skeletonization algorithms, and then proposes its own algorithm (SPTA). All of the described skeletonization algorithms, including SPTA, are based on the concept of passing over the image a square window of three rows and three columns (commonly referred to as a 3.times.3 window). As the square 3.times.3 window is passed across the image, the algorithms evaluate the 8 pixel neighborhood surrounding the center pixel and, based on the evaluation, either convert a black center point to white, or leave it unaltered.
Pattern classification received a boost from another direction with recent advances in the field of connectionism. Specifically, highly parallel computation networks ("neural networks") have come to the fore with the work by Hopfield, disclosed in U.S. Pat. No. 4,660,166, issued Apr. 21, 1987. Also, work continued on robust learning algorithms for multi-layered networks in which "hidden" layers of neural elements permit separation of arbitrary regions of the feature space. This work, reported on, inter alia, by Gullichsen et al. in "Pattern Classification by Neural Networks: An Experimental System for Icon Recognition", Proceedings of the IEEE First International Conference on Neural Networks, pp IV-725-732, Cardill et al., Editors, concentrates on the character classification process. The system they describe uses some image preprocessing but no feature extractions. Instead, they rely entirely on the inherent classification intelligence that the neural networks acquire through the "back propagation" training process. The reported system apparently works, but as suggested by the authors, many questions remained to be investigated. The system's performance is less than acceptable.
There exist many other character classification techniques, approaches, and algorithms. For purposes of this disclosure, however, the above references provide a reasonable description of the most relevant prior art. Suffice it to say that with all the efforts that have gone into solving the character recognition (i.e., classification) problem, the existing systems do not offer the accuracy and speed that is believed needed for a successful commercial system for recognizing hand written symbols.